#include <iostream>
#include <vector>
#include <map>
#include <iomanip>
#include <string>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

template<class T>
class Edge
{
public:
    T src;
    T dest;
    int weight;
public:
    Edge() : weight(0){}
    Edge(T i, T j, int w) : src(i), dest(j), weight(w){}
    ~Edge(){}
};


template<class T>
class UndirGraphMat
{
public:
    map<T, int> Vertices;
    int numVertices = 0;
    vector<vector<int>> adjMatrix;
    vector<Edge<T>> edge;
    vector<T> ver;

public:
    UndirGraphMat() : numVertices(0){}
    UndirGraphMat(vector<T> vertices) : numVertices(vertices.size())
    {
        for(int i=0; i<numVertices; i++)
        {
            Vertices[vertices[i]] = i;
            ver.emplace_back(vertices[i]);
        }
        adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
    }
    ~UndirGraphMat(){}

    void addEdge(T i, T j, int weight=1)
    {
        auto it1 = Vertices.find(i);
        auto it2 = Vertices.find(j);
        
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjMatrix[it1->second][it2->second] = weight;
            adjMatrix[it2->second][it1->second] = weight;
            edge.emplace_back(i, j, weight);
        }
    }

    void removeEdge(T i, T j)
    {
        auto it1 = Vertices.find(i);
        auto it2 = Vertices.find(j);
        
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjMatrix[it1->second][it2->second] = 0;
            adjMatrix[it2->second][it1->second] = 0;
            // 删除edge
        }
    }

    void dfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin();it!=Vertices.end();it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        stack<T> sta;
        sta.push(start);
        while(!sta.empty())
        {
            T cur = sta.top();
            sta.pop();
            if(!visited[cur])
            {
                cout << cur << "  ";
                visited[cur] = true;
                int col = Vertices[cur];
                for(int i=numVertices-1; i>=0; i--)
                {
                    if(adjMatrix[col][i] && !visited[reverVertices[i]])
                    {
                        sta.push(reverVertices[i]);
                    }
                }
            }
        }
        
    }

    void bfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        queue<T> que;
        que.push(start);
        visited[start] = true;
        while (!que.empty())
        {
            T cur = que.front();
            que.pop();
            cout << cur << "  ";
            int col = Vertices[cur];
            for(int i=0; i<numVertices; i++)
            {
                if(adjMatrix[col][i] && !visited[reverVertices[i]])
                {
                    que.push(reverVertices[i]);
                    visited[reverVertices[i]] = true;
                }
            }
        }
        
    }

    void printGraph()
    {
        std::ostringstream oss;
        int maxlen = 0;
        for(auto it : Vertices)
        {
            oss<<it.first;
            maxlen = maxlen < oss.str().length() ? oss.str().length() : maxlen;
        }
        cout<<std::setw(maxlen)<<"";
        for(auto it : Vertices) cout<<std::right<<std::setw(maxlen)<<it.first;
        cout<<endl;
        cout<<std::setw(maxlen)<<"";
        for(int i=0; i<numVertices; i++)
            for(int i=0; i<maxlen; i++) 
                cout<<"-";
        cout<<endl;
        auto it = Vertices.begin();
        for(int i=0; i<numVertices; i++)
        {
            cout<<std::left<<std::setw(maxlen-1)<<it->first<<"|";
            for(int j=0; j<numVertices; j++)
            {
                cout<<std::right<<std::setw(maxlen)<<adjMatrix[i][j];
            }
            cout<<endl;
            it++;
        }
    }

    UndirGraphMat<T> krusKalMST(void)
    {
        vector<Edge<T>> tmpedge(this->edge);
        UndirGraphMat<T> mst(ver);
        map<T, int> parents(Vertices);
        // for(auto it : parents) cout << it.first << "  " << it.second << endl;
        int totalweight = 0;
        sort(tmpedge.begin(), tmpedge.end(), [](Edge<T>& a, Edge<T>& b){return a.weight < b.weight;});
        // for(auto it : tmpedge)
        // {
        //     cout << it.src << " " << it.dest << " " << it.weight <<endl;
        // }
        for(int i=0; i<tmpedge.size(); i++)
        {
            auto tmp1 = parents.find(tmpedge[i].dest)->second;
            auto tmp2 = parents.find(tmpedge[i].src)->second;
            
            if(tmp1!=tmp2)
            {
                mst.addEdge(tmpedge[i].src, tmpedge[i].dest, tmpedge[i].weight);
                
                for(auto it=parents.begin(); it!=parents.end(); it++)
                {
                    if(it->second == tmp1) it->second = tmp2;
                }
                
                totalweight+=tmpedge[i].weight;                
            }
            if(mst.edge.size() == numVertices-1) break;
        }
        printf("%d\n", totalweight);
        return mst;
        
    }

    UndirGraphMat<T> PrimMST(void)
    {
        vector<Edge<T>> tmpedge(numVertices);
        map<T, bool> selected;
        UndirGraphMat<T> mst(ver);
        int totalwight = 0;
        for(int i=0; i<tmpedge.size(); i++)
        {
            tmpedge[i].dest = ver[i];
            tmpedge[i].weight = INT_MAX;
            selected[ver[i]] = false;
        }
        selected[ver[0]] = true;
        T parent = ver[0];
        for(int i=0; i<numVertices-1; i++)
        {
            int argmin = 0;
            int src = Vertices[parent];
            for(int j=0; j<numVertices; j++)
            {
                if(adjMatrix[src][j] && !selected[tmpedge[j].dest])
                {
                    if(adjMatrix[src][j] < tmpedge[j].weight)
                    {
                        tmpedge[j].weight = adjMatrix[src][j];
                        tmpedge[j].src = parent;
                    }
                }
            }
            
            for(int j=0; j<numVertices; j++)
            {
                if(!selected[tmpedge[j].dest] && tmpedge[j].weight < tmpedge[argmin].weight)
                {
                        argmin = j;
                }
            }

            mst.addEdge(tmpedge[argmin].src, tmpedge[argmin].dest, tmpedge[argmin].weight);
            selected[tmpedge[argmin].dest] = true;
            parent = tmpedge[argmin].dest;
            totalwight+=tmpedge[argmin].weight;

        }

        printf("%d\n", totalwight);
        return mst;
    }
    
    int dijkstra(T start, T end)
    {
        vector<Edge<T>> tmpedge(numVertices);
        map<T, bool> selected;
        int minweight = 0;
        int argstart = 0;
        for(int i=0; i<numVertices; i++)
        {
            tmpedge[i].dest = ver[i];
            tmpedge[i].weight = INT_MAX;
            selected[ver[i]] = false;
            if(tmpedge[i].dest == start) argstart = i;
        }
        selected[start] = true;
        T parent = start;
        while(!selected[end])
        {
            int src = Vertices[parent];
            int argmin = argstart;
            for(int i=0; i<numVertices; i++)
            {
                if(adjMatrix[src][i] && !selected[tmpedge[i].dest])
                {
                    if(adjMatrix[src][i]+minweight < tmpedge[i].weight)
                    {
                        tmpedge[i].src = parent;
                        tmpedge[i].weight = adjMatrix[src][i]+minweight;
                    }
                }
            }

            for(int i=0; i<numVertices; i++)
            {
                if(!selected[tmpedge[i].dest] && tmpedge[i].weight<tmpedge[argmin].weight)
                {
                    argmin = i;
                }
            }

            selected[tmpedge[argmin].dest] = true;
            parent = tmpedge[argmin].dest;
            minweight = tmpedge[argmin].weight;
        }
        printf("%d\n", minweight);
        return minweight;


    }

    
};



template<class T>
class DirGraphMat
{
public:
    map<T, int> Vertices;
    int numVertices = 0;
    vector<vector<int>> adjMatrix;
    
public:
    DirGraphMat() : numVertices(0){}
    DirGraphMat(vector<T> vertices) : numVertices(vertices.size())
    {
        for(int i=0; i<numVertices; i++)
        {
            Vertices[vertices[i]] = i;
        }
        adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
    }
    ~DirGraphMat(){}

    void addEdge(T i, T j, int weight=1)
    {
        auto it1 = Vertices.find(i);
        auto it2 = Vertices.find(j);
        
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjMatrix[it1->second][it2->second] = weight;
        }
    }

    void removeEdge(T i, T j)
    {
        auto it1 = Vertices.find(i);
        auto it2 = Vertices.find(j);
        
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjMatrix[it1->second][it2->second] = 0;
        }
    }

    void printGraph()
    {
        std::ostringstream oss;
        int maxlen = 0;
        for(auto it : Vertices)
        {
            oss<<it.first;
            maxlen = maxlen < oss.str().length() ? oss.str().length() : maxlen;
        }
        cout<<std::setw(maxlen)<<"";
        for(auto it : Vertices) cout<<std::right<<std::setw(maxlen)<<it.first;
        cout<<endl;
        cout<<std::setw(maxlen)<<"";
        for(int i=0; i<numVertices; i++)
            for(int i=0; i<maxlen; i++) 
                cout<<"-";
        cout<<endl;
        auto it = Vertices.begin();
        for(int i=0; i<numVertices; i++)
        {
            cout<<std::left<<std::setw(maxlen-1)<<it->first<<"|";
            for(int j=0; j<numVertices; j++)
            {
                cout<<std::right<<std::setw(maxlen)<<adjMatrix[i][j];
            }
            cout<<endl;
            it++;
        }
    }

    void dfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        stack<T> sta;
        sta.push(start);
        while(!sta.empty())
        {
            T cur = sta.top();
            sta.pop();
            int col = Vertices[cur];
            if(!visited[cur])
            {
                cout << cur << "  ";
                visited[cur] = true;
                for(int i=numVertices-1; i>=0; i--)
                {
                    if(adjMatrix[col][i] && !visited[reverVertices[i]])
                    {
                        sta.push(reverVertices[i]);
                    }
                }
            }
        }
    }

    void bfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        queue<T> que;
        que.push(start);
        visited[start] = true;
        while (!que.empty())
        {
            T cur = que.front();
            que.pop();
            cout << cur << "  ";
            int col = Vertices[cur];
            for(int i=0; i<numVertices; i++)
            {
                if(adjMatrix[col][i] && !visited[reverVertices[i]])
                {
                    que.push(reverVertices[i]);
                    visited[reverVertices[i]] = true;
                }
            }
        }
        
    }
};


template<class T>
class UnDirGraphAdjtab
{
public:
    map<T, int> Vertices;
    int numVertices = 0;
    vector<list<T>> adjTable;
public:
    UnDirGraphAdjtab() : numVertices(0){}
    UnDirGraphAdjtab(vector<T> vertices) : numVertices(vertices.size())
    {
        for(int i=0; i<vertices.size(); i++)
        {
            Vertices[vertices[i]] = i;
            adjTable.emplace_back(list<T>{vertices[i]});
        }

    }
    ~UnDirGraphAdjtab(){}

    void addEdge(T v, T w)
    {
        auto it1 = Vertices.find(v);
        auto it2 = Vertices.find(w);
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjTable[it1->second].emplace_back(it2->first);
            adjTable[it2->second].emplace_back(it1->first);
        }
    }

    void printGraph()
    {
        for(list<T> i : adjTable)
        {
            auto it = i.begin();
            cout<<*it<<" -> ";
            for(auto j=next(i.begin(), 1); j!=i.end(); j++)
                cout<<*j<<"  ";
            cout<<endl;
        }
    }

    void dfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        stack<T> sta;
        sta.push(start);
        while(!sta.empty())
        {
            T cur = sta.top();
            sta.pop();
            if(!visited[cur])
            {
                cout << cur << "  ";
                visited[cur] = true;
                int col = Vertices[cur];
                for(typename list<T>::reverse_iterator it=adjTable[col].rbegin(); it!=prev(adjTable[col].rend(),1); it++)
                {
                    if(!visited[(*it)])
                    {
                        sta.push((*it));
                    }
                }

            }
        }
    }

    void bfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
        }
        queue<T> que;
        que.push(start);
        visited[start] = true;
        while(!que.empty())
        {
            T cur = que.front();
            que.pop();
            cout << cur << "  ";
            int col = Vertices[cur];
            for(auto it=adjTable[col].begin(); it!=adjTable[col].end(); it++)
            {
                if(!visited[*it])
                {
                    que.push(*it);
                    visited[*it] = true;
                }
                    
            }
        }
    }

};


template<class T>
class DirGraphAdjtab
{
public:
    map<T, int> Vertices;
    int numVertices = 0;
    vector<list<T>> adjTable;
public:
    DirGraphAdjtab() : numVertices(0){}
    DirGraphAdjtab(vector<T> vertices) : numVertices(vertices.size())
    {
        for(int i=0; i<vertices.size(); i++)
        {
            Vertices[vertices[i]] = i;
            adjTable.emplace_back(list<T>{vertices[i]});
        }

    }
    ~DirGraphAdjtab(){}

    void addEdge(T v, T w)
    {
        auto it1 = Vertices.find(v);
        auto it2 = Vertices.find(w);
        if(it1!=Vertices.end() && it2!=Vertices.end())
        {
            adjTable[it1->second].emplace_back(it2->first);
        }
    }

    void printGraph()
    {
        for(list<T> i : adjTable)
        {
            auto it = i.begin();
            cout<<*it<<" -> ";
            for(auto j=next(i.begin(), 1); j!=i.end(); j++)
                cout<<*j<<"  ";
            cout<<endl;
        }
    }

    void dfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        map<int, T> reverVertices;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
            reverVertices.emplace(it->second, it->first);
        }
        stack<T> sta;
        sta.push(start);
        while(!sta.empty())
        {
            T cur = sta.top();
            sta.pop();
            int col = Vertices[cur];
            if(!visited[cur])
            {
                cout << cur << "  ";
                visited[cur] = true;
                for(auto it=adjTable[col].rbegin(); it!=prev(adjTable[col].rend(), 1); it++)
                {
                    sta.push(*it);
                }
            }
        }
    }

    void bfs(T start)
    {
        if(Vertices.find(start) == Vertices.end()) return ;
        map<T, bool> visited;
        for(auto it=Vertices.begin(); it!=Vertices.end(); it++)
        {
            visited.emplace(it->first, false);
        }
        queue<T> que;
        que.push(start);
        visited[start] = true;
        while(!que.empty())
        {
            T cur = que.front();
            que.pop();
            cout << cur << "  ";
            int col = Vertices[cur];
            for(auto it=adjTable[col].begin(); it!=adjTable[col].end(); it++)
            {
                if(!visited[*it])
                {
                    que.push(*it);
                    visited[*it] = true;
                }
                    
            }
        }
    }

};





int main()
{


    vector<int> nums = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    UndirGraphMat<int> g(nums);
    // DirGraphMat<int> g(nums);
    
    // 添加边 prim验证数据
    // g.addEdge(0, 1, 4);
    // g.addEdge(0, 7, 8);
    // g.addEdge(1, 7, 11);
    // g.addEdge(1, 2, 8);
    // g.addEdge(7, 8, 7);
    // g.addEdge(7, 6, 1);
    // g.addEdge(2, 8, 2);
    // g.addEdge(8, 6, 6);
    // g.addEdge(2, 3, 7);
    // g.addEdge(2, 5, 4);
    // g.addEdge(6, 5, 2);
    // g.addEdge(3, 5, 14);
    // g.addEdge(3, 4, 9);
    // g.addEdge(5, 4, 10);

    // dijstra验证数据
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 7, 3);
    g.addEdge(1, 2, 8);
    g.addEdge(7, 8, 1);
    g.addEdge(7, 6, 6);
    g.addEdge(2, 8, 2);
    g.addEdge(8, 6, 6);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 5, 4);
    g.addEdge(6, 5, 2);
    g.addEdge(3, 5, 14);
    g.addEdge(3, 4, 9);
    g.addEdge(5, 4, 10);

    // vector<char> nums = {'a', 'b', 'c', 'd', 'e'};
    // UndirGraphMat<char> g(nums);



    // g.addEdge('a', 'b');
    // g.addEdge('a', 'c');
    // g.addEdge('b', 'd');
    // g.addEdge('b', 'e');
    // g.addEdge('c', 'd');


    // vector<string> nums = {"a", "ab", "c", "d", "e"};
    // UndirGraphMat<string> g(nums);

	


    // g.addEdge("a", "ab");
    // g.addEdge("a", "c");
    // g.addEdge("a", "d");
    // g.addEdge("ab", "c");
    // g.addEdge("c", "d");
    
    // 打印图
    // UndirGraphMat<int> mst = g.PrimMST();
    // mst.printGraph();
    int mindistense = g.dijkstra(0, 4);
    

    return 0;
}
